// https://leetcode.cn/problems/hanota-lcci/

// 题干：在经典汉诺塔问题中，有 3 根柱子及 N 个不同大小的穿孔圆盘，盘子可以滑入任意一根柱子。
//      一开始，所有盘子自上而下按升序依次套在第一根柱子上(即每一个盘子只能放在更大的盘子上面)。移动圆盘时受到以下限制:
//      (1) 每次只能移动一个盘子;
//      (2) 盘子只能从柱子顶端滑出移到下一根柱子;
//      (3) 盘子只能叠在比它大的盘子上。

// 示例：输入：A = [2, 1, 0], B = [], C = []
//       输出：C = [2, 1, 0]

// 碎语：递归的入门，不如来探讨什么时候想到递归
//       答案是，问题能被拆解成更小的子问题
//       需要在慢慢的做题中领会，以宏观切入，微观探细节

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    void hanota(vector<int>& A, vector<int>& B, vector<int>& C)
    {
        return dfs(A, B, C, A.size()); // hanota函数的参数不够，所以自己创建一个函数
    }

    void dfs(vector<int>& A, vector<int>& B, vector<int>& C, int n)
    {
        // 最小子问题
        if (n == 0){
            return ;
        }
        if (n == 1){
            C.push_back(A.back());
            A.pop_back();
            return ;
        }

        dfs(A, C, B, n - 1);
        C.push_back(A.back()); // 不能写成C[0] = A.back(); 大操作要兼容小操作
        A.pop_back();
        dfs(B, A, C, n - 1);
    }
};

int main()
{
    Solution sol;
    vector<int> A = {2,1,0}, B = { }, C = { };

    sol.hanota(A, B, C);
    for (int& num : C){
        cout << num << " ";
    }
    cout << endl;
    
    return 0;
}